#ifndef INTERVALTREE
#define INTERVALTREE

#include "RedBlackTree.h"
#include "RedBlackTree.templates.h"

template<typename T>
class IntervalTree;

template<typename T>
class IntervalTree : public RedBlackTree<T>
{
 public:
  typedef typename RedBlackTree<T>::Node Node;
 IntervalTree(T _low, T _high): RedBlackTree<T>(_low,_high){};
  IntervalTree() {};
  ~IntervalTree() {};
  void Insert(T _low,T _high);
  int Del(T _low,T _high);
  int IntervalSearch(T _low, T _high) const;
};

template<typename T>
void IntervalTree<T>::Insert(T _low, T _high)
{
  this->insert(_low,_high);
};

template<typename T>
int IntervalTree<T>::Del(T _low,T _high)
{
  Node* x = this->tree_search( _low, _high, this->root);
  this->del(x);
  return 0;
};

template<typename T>
int IntervalTree<T>::IntervalSearch(T _low,T _high) const
{
  Node* x = this->root;
  if (x == this->nil)
    {
      std::cout << "Empty Tree!" << std::endl;
      return 0;
    }
  else
    {
      while(x != this->nil)
	{
	  if(x->right != this->nil && _low > x->right->MAX)
	    {
	      std::cout << "Not Found!" << std::endl;
	      return 0;
	    }
	  else if(x->left != this->nil && x->left->MAX >= _low)
	    {
	      x = x->left;
	      if(_low > x->high or _high < x->low)
		continue;
	      else
		{
		  std::cout << "Found! [" << x->low << "," << x->high << "]" << std::endl;
		  return 0;
		}
	    }
	  else if(x->right != this->nil && x->right->MAX >= _low)
	    {
	      x = x->right;
	      if(_low > x->high or _high < x->low)
		continue;
	      else
		{
		  std::cout << "Found! [" << x->low << "," << x->high << "]" << std::endl;
		  return 0;
		}
	    }
	  else
	    {
	      std::cout << "Not Found!" << std::endl;
	      return 0;
	    }
	}
    }
};
#else
//DO NOTHING
#endif
